#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std;

// 3186. 施咒的最大总伤害
// https://leetcode.cn/problems/maximum-total-damage-with-spell-casting/description/

class Solution
{
public:
    long long maximumTotalDamage(vector<int> &power)
    {
        unordered_map<int, int> freqOfNum;
        for (int i = 0; i < power.size(); i++)
        {
            freqOfNum[power[i]]++;
        }
        vector<pair<int, int>> cntPower(freqOfNum.begin(), freqOfNum.end());
        sort(cntPower.begin(), cntPower.end());
        vector<long long> dp(cntPower.size() + 1);

        for (int i = 0, j = 0; i < cntPower.size(); i++)
        {
            while(cntPower[j].first < cntPower[i].first){
                j++;
            }
            dp[i + 1] = max(dp[i], dp[j] + cntPower[i].first * 1LL * cntPower[i].second);
        }

        return dp[cntPower.size()];
    }
};

int main()
{
    return 0;
}